20220405-TIL

오늘 알고리즘 문제는 2차원 배열의 원소 중 k번째로 작은 수를 구해야 하는 문제였다.

• K번째 수 문제는 매개변수 탐색을 통해 가능한 k의 범위를 줄여가는 식으로 풀었다.
• 처음에는 2차원 배열에 있는 원소들 사이의 대소 관계를 파악하는 식으로 접근했다.
  (A[i][i] 를 기준으로 k번째 수의 범위를 파악 -> n >= 5 일 때부터 문제가 생김..)
• 탐색 범위를 줄일 방법이 안 떠올라서, 결국엔 질문 게시판에서 힌트를 보고 풀었다.
• 배열 B에 대한 범위가 아닌, k번째 수 자체의 범위를 구하는 것이 핵심인 문제였다..
  (f(x) = 2차원 배열 A에 있는 x보다 작은 원소의 개수 -> x에 대해서 매개변수 탐색)